\documentclass[10pt, a4paper, twoside, final, onecolumn]{icton2010}
%\documentclass[10pt, draftcls, onecolumn] {IEEEtran}
%\documentclass[12pt,a4paper]{article}
%\textwidth 16.0 cm
%\textheight 24.7 cm
\IEEEoverridecommandlockouts \overrideIEEEmargins
\usepackage{amsmath}
\usepackage{epsfig}
%\interdisplaylinepenalty=2500
\usepackage{array}
\usepackage{placeins}
\usepackage{url}
\usepackage{enumerate}
\usepackage[centerlast]{caption}
%\usepackage{listings}
\usepackage{cite}
\usepackage{pslatex}
% \newif\iflong\longtrue
\usepackage[pdftex]{hyperref}  % so we can generate nice pdf
\hypersetup{pdftex,
            backref=true,
            hyperindex=true,
            colorlinks=true,
            linkcolor=black,citecolor=black,filecolor=black,urlcolor=black,
            bookmarks=true,
            breaklinks=true
            }
\usepackage{graphicx}
\usepackage{url}
\pagestyle{empty}
\title{Optimizing Multi-Layered Networks Towards a Transparently Optical Internet }
\author{Ronald G. Addie${}^{*}$, David Fatseas${}^{*}$ and Moshe Zukerman${}^{\dag}$\\
${}^{*}$~University of Southern Queensland, Australia,
{\tt addie@usq.edu.au, david\_fatseas@yahoo.com}\\
${}^{\dag}$ Electronic Eng. Dept., City University of Hong Kong,
Hong Kong SAR, {\tt m.zu@cityu.edu.hk} }
\date{\today}
\begin{document}
\maketitle
\thispagestyle{empty}

\begin{abstract}

\noindent Data transported on the Internet is handled by various
technologies at different layers. The move towards an optically
transparent internet will accelerate when it is justified by the
cost structure of the various technologies. In this paper we
describe a unified optimization framework for multiple technologies
that interwork together based on the following assumptions: (i)
every layer is associated with a unique technology, (ii) traffic can
be modeled as a Poisson stream of {\em flows}, (iii) a flow will be
served by a layer (technology) on a least-cost basis. This way
traffic is split between the layers and if, under a given cost
structure, a layer (e.g. IP) is found to have no ``customers''
(flows) because it is too costly relative to other layers (e.g.
WDM), it will be excluded. In addition to technology choices we also
optimize link dimensioning and virtual topology.
\end{abstract}

\begin {keywords}
network optimization, traffic engineering,  network evolution,
layered architecture, traffic modeling.
\end{keywords}

\section{Introduction}

The currently evolved Internet architecture is based on a variety of
technologies and serves numerous services and traffic types.
Internet design that will minimize cost subject to meeting quality
of service (QoS) requirements of the various services requires
simultaneous optimization of (1) technology choices, (2) virtual
topology, and traffic engineering (including traffic grooming). It
is clear that
 optimizing the
entire Internet from all these three aspects is too difficult given
its size, the multiple domains, the wide range of technology options
and the unpredictable and complex nature of the traffic.

There are many papers which propose mathematical programming
formulations for network design (e.g. \cite{Ramaswami96design})
however these are applicable only to small networks and only
consider a subset of the above problems. This limitation is also
applicable to {\em some} heuristics that have been proposed (e.g.
\cite{Zhu02Traffic,Sridharan02Practical}), that are not scalable to
large problems. Furthermore, when a large number of technologies are
considered simultaneously, formulation of the design problem as a
mathematical program is a task of massive complexity, and its
solution, if it can be obtained, cannot be intuitively understood.

The book \cite{Zhu05Traffic} adopts a formulation of the network
design problem in terms of a problem of optimal routing through a
multi-layered network (or a multi-layered graph). This is quite
similar to our approach. However, our objective includes technology
choices, and dimensioning of the physical layer as part of the
problem, whereas \cite{Zhu05Traffic} assumes that the physical layer
is given, and a specific collection of grooming technologies is
available, so the task to be solved is how to route traffic through
this network. Also, we adopt a statistical model of traffic adopting
a Pareto distribution for flows, whereas \cite{Zhu05Traffic}
analyses a scenario rather than a statistical model.
%Also,
%\cite{Zhu05Traffic} takes the constraint that the same wavelength
%can be used once only in each fiber into account whereas we do not.
%Taking account of this constraint is too detailed at this stage
%of the development of our model.

\subsection{A Unified Layered Routing Model}

In this paper we propose and develop a unified framework for
multiple technologies that interwork together under realistic
assumptions of traffic demand. To do this we adopt a simple model
based on the principle that (i) each layer is associated with a
unique technology (e.g. IP, ATM, WDM, or more specific grooming
techniques); (ii) traffic can be modelled as a Poisson stream of
independently distributed {\em flows}; and (iii) each flow is routed
on the least-cost path {\em for this flow size} in each layer
(technology). Each layer provides the ``service'' of passing a
request from the layer above directly to the layer below. Sometimes
this is the cheapest way to fulfil a service request. Hence,
adopting least-cost paths in each layer ensures that the least-cost
technology will be used to route traffic.

A new technology can be incorporated into this model by choosing a
collection of parameters which determine, for each layer, what it
will cost to deliver a certain type of traffic and how traffic will
be {\em split} between layers when there is a choice. Each layer is
a network in its own right, and the links of layer $n+1$ correspond
to the traffic streams of layer $n$. We then use shortest-path
routing as the design principle for each layer, so the design of
each layer is {\em almost} independent from the design of other
layers.

However, since the cost of links in layer $n+1$
is determined by the cost of the whole path that these links follow,
in layer $n$, the traffic in layer $n+1$ will change with
the costs in layer $n$, and this will cause the traffic in layer $n$ to change
and hence the costs in layer $n$ will change again.
An iterative scheme for designing all the layers
appears to converge, in our experiments, quite quickly,
although the experiments are at an early stage.

\subsection{Layered Routing}

For simplicity we assume that all nodes are {\em capable} of the
switching and routing of all the layers, i.e. each node is
equipped with all technologies. If it turns out that at a certain
node no switching of a given type occurs there, then clearly we do
not need to install that technology at that node. Physical
transmission occurs only at layer 0. Links at higher layers are
composed of paths through the layer beneath. Any path, between any
pair of nodes in layer $k$, is a possible link in layer $n>k$,
however in many cases it will transpire that for reasons a given
pair is not connected. Every layer provides, as a bare minimum, the
service of merely providing access to the links of the layer below,
at no extra cost. If this is the only function provided in a certain
layer, after the network design algorithm has completed its work,
this means that the design has determined that the technology
corresponding to this layer is not cost effective and will not be
installed at all. For example, due to the excessive cost of
handling individual packets in the IP layer \cite{RefWorks:3370},
it may be more cost effective to delegate switching (possibly optical
switching) to lower layers under a given future cost structure.


\subsection{Cost of Communication and Flows}

Internet cost can be classified into three categories:
\begin{enumerate}
\item   Data processing: In the IP layer this category includes costs of equipment, maintenance and energy
associated with individual packet processing in routers (including
repeated buffering and routing-table look-up) which is energy
inefficient  \cite{RefWorks:3370} especially for large flows. In
lower layers these will include for example cost of add-drop
multiplexers (ADMs).
\item  Connection set-up, including
recording and updating hash tables in flow-based routing, or the
setup cost for an SDH or WDM paths in cases where those are used.
\item  Transmission.
\end{enumerate}



In line with these three categories, we distinguish three size-based
flow types:
  \begin{enumerate}
\item   Mice: these are the small flows
for which any flow setup cost will be more significant than any
per-packet or per-byte costs. Their number is large and it may be
optimal to route them in pre-set existing tunnels - possibly a
lightpath. They are
 Their tunnels may be longer
than shortest path (similar to busses that drop off and take up
passengers along their routes).

\item   Elephants: these are large flows
for which, the flow setup cost will be insignificant. Their numbers
are relatively small, so they justify complex flow setup and
clear-down, possibly including the setup of a routed wavelength.
Individual packet processing is avoided.

\item   Kangaroos: they are flows that are larger than the mice and
smaller than the elephants where the connection set-up cost is
neither negligible nor significantly larger than their data
processing cost. It may be beneficial to route them based on the
current IP architecture and to use shortest-hop-path routing for
them because their packets are treated individually at every router.
\end{enumerate}

% \iflong
% \input{costtests.tex}
% \fi

\section{The Traffic Model} \label{traffic}

We will assume that all traffic is formed as a collection of flows
and that the flow sizes are independent Pareto or truncated Pareto
distributed, as described in the next subsection. The arrival
process of the flows are assumed to follow a Poisson process.

\subsection{Flow Size Distribution}\label{truncpareto}

We assume that traffic is either continuous at a fixed rate, or is
made up of a Poisson stream of flows, of rate $\lambda$, which have
a truncated (or untruncated) Pareto distribution with shape
parameter $\gamma$, with minimum size $\delta$ and maximum size $D$.
(We allow for $D$ to be arbitrarily large ($D=\infty$) so the case
of untruncated Pareto distribution is included.) Assuming that flow
sizes are measured in bits, the probability that a randomly selected
flow with the truncated (or untruncated) Pareto distribution with
these parameters is shorter than $t$ is
\begin{equation}\label{truncparetoprob}
\begin{cases}
0,&t<\delta,\\
{\left(D\over t\right)^{-\gamma} - \left(D \over \delta\right)^{-\gamma}
\over 1-\left(D \over \delta\right)^{-\gamma}}, & \delta \le t < D, \\
1,&t \ge D.\\
\end{cases}
\end{equation}


The mean bit rate of such a Poisson
stream of flows is
\begin{equation}\label{truncparetorate}
{\lambda\gamma\left(\delta^{1-\gamma}-D^{1-\gamma}\right)\over(\gamma-1)\left(\delta^{-\gamma}-D^{-\gamma}\right)}.
\end{equation}

\section{Fixed-Point Algorithm for Link Capacity Assignment}

A simple and effective way to evaluate the performance of
telecommunications networks is to use an approach involving {\em
fixed point iterations}. The behavior of traffic is affected by the
capacity of the links, switches, and routers that it passes through,
and also by the other traffic that uses the same resources at the
same time. Given all the conditions which apply, relatively simple
models can be used to predict the performance and behavior of one
traffic stream. A fixed-point algorithm can then be used to predict
the behavior and performance of the complete collection of traffic
streams which share a network by successively replacing the traffic
streams by streams which exhibit their behavior in the presence of
the other traffic.

Fixed-point algorithms have been used extensively in performance
evaluation of telecommunications network. One example is the
so-called
 {\it
Erlang fixed-point approximation} (EFPA) method. It is based on
decoupling the given system into independent server groups
(subsystems) and computing blocking probability for each subsystem
independently. EFPA was first proposed in \cite{cooper64} in 1964
for the analysis of circuit-switched networks and has been
extensively used since then in network analyzes and design. See e.g.
\cite{rosberg2003} and references therein.

In this paper our objective is not to estimate blocking
probabilities but instead to estimate required capacities.
Therefore, instead of iterating until convergence of loss
probabilities has occurred, we adjust capacities at each iteration,
and continue iterating until capacities have converged. Whereas in
the EFPA the Erlang B formula is used to estimate loss, in the fixed
point iteration presented here simple formulae (e.g.,  mean traffic
plus $3\times$ standard deviation of traffic) are used to estimate
the capacity required to achieve a certain target for loss on each
link.

Alternative approaches are used for link dimensioning based on the
following link classifications.
\begin{itemize}
\item Links which carry only traffic representing permanent virtual
links of a specified capacity (constant bitrate or peak rate
allocated). There the required capacity is obtained by simply
summing the capacity required and rounding up to the next module
size. \item Links where traffic is statistically random, but they
are not the bottleneck for any of the streams that pass through
them. Such links are typically located in the core network and their
streams are bottlenecked typically at the access. For them, the
required capacity is the mean traffic plus three standard
deviations. The traffic variance is estimated by adopting a Poisson
model for the number of active flows, in which the {\em rate}
exhibited by each flow is assumed to be the rate of the maximin link
feeding traffic into this link, i.e. the maximum over all the
traffic streams, of the minimum speed of all the links used by that
traffic stream. If this maximin rate is denoted by $r_{mm}$, and the
rate of the link is $r_L$, the variance of the rate of transmission
over the link -- using a Poisson model -- is $r_{mm}r_L$.
\item For each one of the remaining links, some traffic streams experience
the link as their bottleneck link. Such links are typically located
in the access network. The link behavior is governed by fair
queueing, and therefore we adopt for them a utilisation target
(which may be different in each layer).
\end{itemize}

% \iflong
% \input{dimtests.tex}
% \fi

\section{Analysis of Layered Networks} \label{layeredfpoint}

The basic fixed-point algorithm described in the previous section
can be extended to layered networks so long as we have a scheme for
splitting traffic between layers. Splitting the type of traffic
described in Section \ref{traffic} is straightforward so long as the
only criterion used for deciding which way to direct traffic is flow
size.

\subsection{Layered Architecture}

The most important principle of layered network architecture is that
{\em each layer of a network employs services provided by layers
below to provide services to the layers above}. Sitting on top of
this layer-cake of services are the demands from the users, which we
refer to in this paper as {\em traffic streams}. Traffic from these
user-generated traffic streams is carried by assigning it to {\em
paths} through the layer at the top. When there is a layer below
this top layer, it is employed for one and only one reason: to
implement links at the top layer. There are three distinct ways in
which layer $n$ can implement a link between node $A$ and node $B$
at layer $n+1$:
\begin{enumerate}[(i)]
\item layer $n$ already has a link between $A$ and $B$ and it simply passes on this service,
at no extra charge, to the layer above; when a link from $A$ to $B$ already exists, and is
not overutilized, this will always the best way to provide the link from $A$ to $B$ at
layer $n+1$.
\item \label{staticvlink}layer $n$ does not have a link from $A$ to $B$  but it has a path from $A$ to $B$
which it can permanently package as a link, for layer $n+1$ (e.g. a
lightpath at the optical layer can be viewed as a link at the IP
layer).
\item  \label{dynamicvlink}layer $n$ does not have a link from $A$ to $B$ but it can dynamically set up,
as required, a path through its network from $A$ to $B$.
\end{enumerate}

There is usually a significant extra cost in making use of links
provided by the mechanisms (\ref{staticvlink}) and
(\ref{dynamicvlink}). In Case (\ref{staticvlink}), this cost is mainly due
to the fact that modularity requirements in Layer $n$ will mean that
the capacity of the path set up through this layer might be
considerably more than is actually needed. In Case
(\ref{dynamicvlink}) the cost is due to the fact that every time a
Layer $n+1$ is set up, a significant cost is incurred. Modularity
always restricts the use of paths through Layer $n$, however in Case
(\ref{dynamicvlink}) we can assume that the path is fully utilized
while the link is in use, so we can neglect this cost in Case
(\ref{dynamicvlink}). Since all the traffic carried by layer $n$ is
derived from one of these three mechanisms, the traffic streams in
layer $n$ correspond, in effect, to the links in layer $n+1$.

\subsection{Splitting }\label{splitting}

Suppose the overall rate of flows is $\lambda$ with a range of flow
sizes from $\delta$ to $\infty$, and suppose that traffic is split
on the basis of whether a flow is bigger or smaller than $D$. If the
flow rate of flows less than size $D$ is $\lambda_1$, then the
traffic of these smaller flows will now have the standard model, but
with rate $\lambda_1$, and flows in the range $\delta$ to $D$. The
other traffic stream will have a rate of $\lambda-\lambda_1$ and a
range of flow sizes from $D$ to $\infty$.

\subsection{Merging}


The parameters of a merged stream that we need to choose are: (i)
the flow arrival rate; (ii) the minimal flow size $\delta$; and
(iii) the maximum flow size $D$. (We assume that all traffic
exhibits a common power law, with exponent $\gamma$.)


% \subsubsection*{Merging}

\iffalse
\begin{enumerate}[I. ]
\item If either of the two streams has longest flow set to infinity, we
must adopt this as the upper flow size for both streams.
\item The flow arrival rate of the merged stream should be the sum of the
arrival rates of the component streams.
\item The mean byte rate of the merged stream must be the sum of the byte
arrival rate of the component streams.
\item The minimum flow size of the merged stream must be greater than
or equal to the minimum of the minimum flow sizes of the component
streams and the maximum flow size of the merged stream should be less
than or equal to the maximum of the maximum flow sizes of the component
streams.
\end{enumerate}
\fi

In order to determine the parameters of a merged traffic stream
we adopt the principle that the flow rate of the merged stream should
be the sum of the flow rates of the component streams, the maximum
flow size should be the maximum of the maximum flow sizes of the component
streams, and the mean bit-rate of the merged stream should be the sum
of the bit-rates of the component streams.

It follows that we have precisely one free parameter, the minimum
flow size, with which to ensure that the mean bit-rate is correctly
matched. Since the mean of a Poisson stream of truncated (or
untruncated) Pareto
flows is given by (\ref{truncparetorate}), % and assuming that $D\gg\delta$,
if the mean rate of such a traffic stream is $m$, the $\delta$ required to match this is the solution of
\begin{equation}
\nonumber m = {\lambda\gamma\left(\delta^{1-\gamma}-D^{1-\gamma}\right)\over(\gamma-1)\left(\delta^{-\gamma}-D^{-\gamma}\right)}.
\end{equation}
Rearranging this gives:
\begin{equation}
\nonumber\delta = {m(\gamma-1)\left(1-(D/\delta)^{-\gamma}\right) \over \lambda\gamma (1-(D/\delta)^{1-\gamma})},
\end{equation}
which can be used repeatedly to solve for $\delta$ quite quickly.

% \iflong
% \input{splittingmerging.tex}
% \fi
 
\section{Implementation}

 An algorithm for network design of a layered network was
described and this algorithm has been implemented (see
\cite{netml2,atnac06,netml4design}) and some preliminary experiments
carried out. The experiments confirm that the network design
algorithm converges quickly for very large networks.


\section{Conclusion}
We have outlined a unified optimization framework for a multi-layer
network that facilitate choice of technologies link dimensioning and
design of virtual topology. More details on the software that is
being developed and implementations for specific scenarios are
available in \cite{netml2,atnac06,netml4design}. 


\bibliographystyle{../erlang/IEEEtran}
%\bibliographystyle{plain}
\bibliography{../ofs/ofs,netml,OPC_bib,opt_top,all}
\end{document}
